package teaching;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-13
 * Time: 18:03
 */

//Merge 归并排序
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int[] tmp = new int[arr.length]; //额外空间
        mergeSort(arr,0, arr.length-1,tmp);

        System.out.println(Arrays.toString(arr));
    }

    //分＋和
    public static void mergeSort(int[] arr,int left,int right,int[] tmp){
        if (left < right){
            int mid = (left + right) /2;
            //先向左边递归
            mergeSort(arr,left,mid,tmp);
            //向右进行递归
            mergeSort(arr,mid+1,right,tmp);
            //到合并
            merge(arr,left,mid,right,tmp);
        }
    }





    //合并的方法

    /**
     *
     * @param arr 排序的原始数组
     * @param left 左边的有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param tmp 中转的数组
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
        int i = left; //初始化i 左边有序序列的初始索引
        int j = mid+1; //初始化j 右边有序序列的初始化索引
        int t = 0; //中转数组的索引

        //(1.)
        //先把左右两边的(有序)的数据 按照规则填充到tmp数组中
        //直到左右两边的有序序列，有一边处理完毕为止

        while (i<=mid && j<=right){
            if (arr[i] < arr[j]){
                //如果左边的有序序列 当前元素 小于等于右边的序列当前元素
                //即将左边的当前元素，拷贝考tmp数组中
                //然后后移
                tmp[t] = arr[i];
                t += 1;
                i += 1;
            }else {
                //反之  那么就是右边的小
                //那么将右边的填充进去tmp
                tmp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }


        //(2.)
        //把有剩余的数据一边依次填充到tmp中
        while (i <= mid){
            //左边的有序序列还有剩余的元素 全部填充到tmp
            tmp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right){
            //左边的有序序列还有剩余的元素 全部填充到tmp
            tmp[t] = arr[j];
            t += 1;
            j += i;
        }

        //(三)
        //将tmp数组的元素拷贝到arr
        //并不是所有都拷贝
        t = 0;
        int tmpLeft = left;

        while (tmpLeft <= right){
            arr[tmpLeft] = tmp[t];
            t += 1;
            tmpLeft += 1;
        }
    }
}
